정보과학회 컴퓨팅의 실제 논문지 (KIISE Transactions on Computing Practices)
Current Result Document :
| 한글제목(Korean Title) |
관계형 데이터베이스 상에서 사용하는 최단 경로 탐색 알고리즘(ALT) 설계와 구현 |
| 영문제목(English Title) |
Design and Implementation of Shortest Path Search Algorithm(ALT) for Relational Database |
| 저자(Author) |
이용현
임동혁
구해모
김형주
YongHyun Lee
DongHyuk Im
Heymo Kou
Hyoung-Joo Kim
|
| 원문수록처(Citation) |
VOL 25 NO. 04 PP. 0215 ~ 0222 (2019. 04) |
한글내용
(Korean Abstract) |
최단 경로 탐색은 교통 정보, 네비게이션, 컴퓨터 네트워크 등 그래프로 표현될 수 있는 다양한 도메인에서 사용되는 주제이다. 빅데이터 시대가 도래함에 따라 이러한 그래프 데이터들은 과거에 비해 그 정보와 크기가 비교 불가능할 정도로 커지고 있다. 이에 따라 보다 큰 그래프를 효과적으로 탐색 및 분석할 필요성이 대두되었다. 이를 해결하고자 데이터베이스 내부에서 직접 그래프 분석을 하는 여러 연구들이 진행되어 왔다. 본 논문에서는 최단 경로를 관계형 데이터베이스 내부에서 직접 휴리스틱하게 탐색하는 In-RDBMS ALT 알고리즘(A* 알고리즘, Landmark, Triangle Inequality)을 제안한다. 또한 기존의 In-RDBMS 최단 경로 탐색 기법과의 성능 비교를 통하여 In-RDBMS ALT 알고리즘의 효율성에 대해서도 논의해보고자 한다.
|
영문내용
(English Abstract) |
Shortest path search is a major topic in various domains that can be represented by graphs such as traffic information, navigation and computer network. As we approach the age of big data, these graph data and information are getting larger and larger in size compared to the past. Therefore, there is the need to effectively search and analyze large graph data. In order to solve this problem, there have been several researches on graph analysis directly in the database. In this study, an In-RDBMS ALT algorithm(A* algorithm, Landmark, Triangle Inequality) that heuristically searches the shortest paths directly in relational database is proposed. The efficiency of In-RDBMS ALT algorithm is also discussed through comparison with existing In-RDBMS shortest path search algorithm.
|
| 키워드(Keyword) |
ALT 알고리즘
최단 경로 탐색
In-DB 분석
관계형 데이터베이스
ALT algorithm
single-source-shortest path
in-db analysis
relational database
|
| 파일첨부 |
PDF 다운로드
|
